/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-search
   @Language: C++
   @Datetime: 16-02-09 08:51
   */

class Solution {
	bool existcore(vector<vector<char> > &board,int row,int col
			,vector<vector<bool> > &vist,string word,int pos){
		if (pos==word.length()) return true;
		if (row<0 || row>=board.size() || col<0 || col>=board[0].size())
			return false;
		if (vist[row][col] || board[row][col]!=word[pos]) return false;

		vist[row][col]=true;
		if(existcore(board,row-1,col,vist,word,pos+1)
				||existcore(board,row,col-1,vist,word,pos+1)
				||existcore(board,row+1,col,vist,word,pos+1)
				||existcore(board,row,col+1,vist,word,pos+1))
			return true;
		return vist[row][col]=false; 
	}

public:
	/**
	 * @param board: A list of lists of character
	 * @param word: A string
	 * @return: A boolean
	 */
	bool exist(vector<vector<char> > &board, string word) {
		// write your code here
		if (word.length()==0) return true;
		if (board.size()==0 || board[0].size()==0) return false;

		int row=board.size(), col=board[0].size();
		vector<vector<bool> > vist(row,vector<bool>(col,false));
		for(int i=0; i<row; ++i)
			for(int j=0; j<col; ++j)
				if (board[i][j]==word[0] && existcore(board,i,j,vist,word,0))
					return true;
		return false;
	}
};
